package utils.perfectHash;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;



import com.google.common.base.Equivalence;

//implemented from http://remis-thoughts.blogspot.de/2012/03/perfect-hashes-in-java-given-set-of-m.html


public class BMZ<E> extends Equivalence<E> implements Serializable{

	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;

	
	private final int seed1;
	private final int seed2;
	private final int[] g;
	
	
	
	public int getSeed1() {
		return seed1;
	}

	public int getSeed2() {
		return seed2;
	}

	BMZ(int seed1, int seed2, int[] g){
		this.seed1= seed1;
		this.seed2= seed2;
		this.g= g;
	}
	
	@Override
	protected boolean doEquivalent(E arg0, E arg1) {
		return arg0.equals(arg1);
	}

	@Override
	protected int doHash(E arg0) {
		int[] hashes= getTwoHashes(arg0, seed1, seed2 ,g.length);
		return g[hashes[0]] + g[hashes[1]];
	}
	
	private static int[] getTwoHashes(Object arg0, int seed1, int seed2, int n){
		int hc= arg0.hashCode();
		int h1= (hc ^ seed1) % n;
		int h2= (hc ^ seed2) % n;
		if(h1==h2){
			++h2;
		}
		if(h1 < 0) {
			h1+= n;
		}
		if(h2 < 0){
			h2+= n;
		}
		return new int[]{h1, h2};
	}
	
	public static <E> Equivalence<E> createBMZ(
		Collection<? extends E> keys,
		int maxTries,
		double c){
		
		Random r= new Random(616);
		int tries=0;
		for(; tries< maxTries;++tries){
			if(tries%100==0){
				System.err.print("createBMZ: "+tries+"\r");
			}
			int seed1= r.nextInt();
			int seed2= r.nextInt();
			int[] g= new int[(int)Math.ceil(c* keys.size())];
			
			Graph graph= toGraph(keys, seed1, seed2, g.length);
			if(graph== null){ //duplicates ==> new seeds
				continue;
			}
			BitSet criticalNodes= findCriticalNodes(graph, g.length);
			BitSet ae= new BitSet(g.length);
			if(!assignIntegersToCriticalVertices(graph, g, ae, criticalNodes)){
				continue; //try again from the start with different seeds 
			}
			assignIntegersToNonCriticalVertices(graph, g, ae, criticalNodes); //this can't fail
			return new BMZ<E>(seed1, seed2, g);
		}
		System.err.println("createBMZ: "+tries);
		throw new IllegalStateException("giving up - perfect hashcode too hard to find!");
	}
	
	
	public static <E> Equivalence<E> create(Collection<? extends E> keys){
		return createBMZ(keys, 10000, 1.15);
	}
	
	/** process everything in the list and all vertices reachable from it */
	private static void assignIntegersToNonCriticalVertices(Graph graph, int[] g, BitSet ae, BitSet criticalNodes){
		List<Integer> toProcess= new LinkedList<Integer>();
		for(int v= criticalNodes.nextSetBit(0);v!=-1;v=criticalNodes.nextSetBit(v+1)){
			toProcess.add(v);
		}
		BitSet visited= (BitSet) criticalNodes.clone();
		processNonCriticalNodes(toProcess, graph, ae, visited, g); //process the critical nodes
		//we've done everything reachable from teh critical nodes - but 
		// what about isolated chains?
		for(int v= visited.nextClearBit(0); v!= -1 && v < g.length; v= visited.nextClearBit(v+1)){
			toProcess.add(v);
			processNonCriticalNodes(toProcess, graph, ae, visited, g);
		}
	}
	
	/** process everythinig in the list and all vertices reachable from it */
	private static void processNonCriticalNodes(List<Integer> toProcess, Graph graph, BitSet ae, BitSet visited, int[] g){
		int nextEdge= ae.nextClearBit(0);
		while(!toProcess.isEmpty()){
			int v= toProcess.remove(0);
			if(v<0){
				continue; // there are no critical nodes
			}
			if(graph.adjacencyList[v] != null){
				for(int adjacent : graph.adjacencyList[v]){
					if(!visited.get(adjacent) && v!=adjacent){ // shouldn't have loops - only if one key 
						// we must give it a value
						g[adjacent] = nextEdge - g[v]; //i.e g[v] + g[a] = edge as needed
						toProcess.add(adjacent);
						ae.set(nextEdge);
						nextEdge= ae.nextClearBit(nextEdge + 1); 
					}
				}
			}
			visited.set(v);
		}
	}
	
	/**
	 * 
	 * @param graph
	 * @param g
	 * @param ae
	 * @param criticalNodes
	 * @return false if we couldn't assign the integers
	 */
	private static boolean assignIntegersToCriticalVertices(Graph graph, int[] g, BitSet ae, BitSet criticalNodes){
		int x= 0;
		List<Integer> toProcess= new LinkedList<Integer>();
		BitSet assigned= new BitSet(g.length);
		while(!assigned.equals(criticalNodes)){
			BitSet unprocessed = ((BitSet)criticalNodes.clone());
			unprocessed.andNot(assigned);
			toProcess.add(unprocessed.nextSetBit(0)); //start at the lowest unassigned critical vertex
			//assign another "tree" of vertices - not all critical ones are necessarily connected!
			x = processCriticalNodes(toProcess, graph, ae, g, x, assigned, criticalNodes);
			if(x < 0){
				return false; //x is overloaded as a failure signal
			}
		}
		return true;
	}
	
	/**
	 * DOES THIS REALLY HAVE TO BE A SEPARATE METHOD?
	 * @param toProcess
	 * @param graph
	 * @param ae
	 * @param g
	 * @param x
	 * @param assigned
	 * @param criticalNodes
	 * @return process a single "tree" of connected critical nodes, rooted at the vertex in toProcess
	 */
	private static int processCriticalNodes(List<Integer> toProcess, Graph graph, BitSet ae, int[] g, int x, BitSet assigned, BitSet criticalNodes){
		while(!toProcess.isEmpty()){
			int v= toProcess.remove(0);
			if(v < 0 || assigned.get(v)){ //there are no critical nodes || already done this vertex
				continue;
			}
			if(graph.adjacencyList[v] != null){
				x= getXThatSatisfies(graph.adjacencyList[v], x, ae, assigned, g);
				for(Integer adjacent : graph.adjacencyList[v]){
					if(!assigned.get(adjacent) && criticalNodes.get(adjacent) && v!=adjacent){
						//give this one an integer, and note we shouldn't have loops - except if there is one key
						toProcess.add(adjacent);
					}
					if(assigned.get(adjacent)){
						int edgeXtoAdjacent= x+ g[adjacent]; //if x is ok, then this edge is now taken
						if(edgeXtoAdjacent >= graph.edges.size()){
							return -1; // this edge is too big! we're only assigning between 0 and m-1
						}
						ae.set(edgeXtoAdjacent);
					}
				}
			}
			g[v]= x;
			assigned.set(v); //assign candidate x to g
			++x;
		}
		return x; // will use this as a candidate for other "trees" of critical vertices
	}
	
	private static int getXThatSatisfies(List<Integer> adjacencyList, int x, BitSet ae, BitSet assigned, int[] g){
		for(Integer adjacent : adjacencyList){
			if(assigned.get(adjacent) /* only covers critical nodes */ && ae.get(g[adjacent] +x)){
				//if we assign x to v, then teh edge between v and 'adjacent' will
				// be a duplicate - so our hash code won't  be perfect! Try again with a new x:
				return getXThatSatisfies(adjacencyList, x+1, ae, assigned, g);
			}
		}
		return x; // this one satisfies all edges
	}
	
	private static BitSet findCriticalNodes(Graph graph, int n){
		// calculate node degrees...
		int[] degrees= new int[n];
		for(Edge edge : graph.edges){
			++degrees[edge.a];
			++degrees[edge.b];
		}
		//... and trim the chains...
		List<Integer> degree1= new LinkedList<Integer>();
		for(int i=0; i<n; ++i){
			if(degrees[i]==1){
				degree1.add(i);
			}
		}
		
		while(!degree1.isEmpty()){
			int v= degree1.remove(0);
			--degrees[v];
			
			if(graph.adjacencyList[v] != null){
				for(int adjacent : graph.adjacencyList[v]){
					if(--degrees[adjacent] == 1){
						degree1.add(adjacent);
					}
				}
			}
		}
		// ... and return a bitmap of critical vertices
		BitSet ret=  new BitSet(n);
		for(int i=0;i<n;++i){
			if(degrees[i]>1){
				ret.set(i);
			}
		}
		return ret;
	}
	
	private static final class Edge {
		final int a,b;
		Edge(int[] ab){
			this.a= ab[0];
			this.b=ab[1];
		}
		
		public String toString() {
			return String.format("(%d,%d)", a, b);
		}
	}

	private static final class Graph{
		final List<Edge> edges;
		/** indexed by vertex, holds list of vertices that a vertex is connected to */
		final List<Integer>[] adjacencyList;
		
		Graph(int n, int m){
			this.edges= new ArrayList<Edge>();
			this.adjacencyList= new List[n];
		}
		
		/**
		 * 
		 * @param e
		 * @return true if this edge is a duplicate
		 */
		boolean addEdge(Edge e){
			edges.add(e);
			if(getAdjacencyList(e.a).contains(e.b)){
				return true;
			}
			getAdjacencyList(e.a).add(e.b);
			getAdjacencyList(e.b).add(e.a);
			return false;
		}
		
		private List<Integer> getAdjacencyList(int forVertex){
			List<Integer> ret= adjacencyList[forVertex];
			return ret == null ? (adjacencyList[forVertex]= new LinkedList<Integer>()) : ret;
		}
	}
	
	private static Graph toGraph(Collection<?> objects, int seed1, int seed2, int n){
		Graph ret= new Graph(n, objects.size());
		for (Object object : objects){
			if(ret.addEdge(new Edge(getTwoHashes(object, seed1, seed2, n)))){
				return null;
			}
		}
		return ret;
	}

}

